package uk.org.landeg.euler.problems.lib;

import java.util.Arrays;

public class CombinationGenerator {
	final int [] elements;
	long [] factorials;
	final int n; // number of elements
	
	public CombinationGenerator(int n) {
		this.n = n;
		elements = new int[n];
		initFactorials();
		for (int idx=0 ; idx < n ; idx++) {
			elements[idx] = idx;
		}
	}
	
	public CombinationGenerator(int[] elements) {
		this.n = elements.length;
		this.elements = new int[elements.length];
		initFactorials();
		System.out.println(Arrays.toString(factorials));
		for (int idx=0 ; idx < n ; idx++) {
			this.elements[idx] = elements[idx];
		}
	}	
	
	private void initFactorials () {
		factorials = new long[n];
		long factorial = 1;
		factorials[factorials.length - 1] = 1;
		for (int idx = factorials.length-2 ; idx >= 0 ; idx--) {
			factorials[idx] = factorials[idx + 1] * factorial++;
		}
	}
	
	public int[] getCombination (int m) {
		int elmt[] = Arrays.copyOf(elements, elements.length);
		int ret[] = new int[n];
		int select = 0;
		try {
			for (int idx = 0 ; idx < n ; idx++) {
				if (idx >= ret.length || select >= ret.length) {
					return null;
				}
				select = (int)(m/factorials[idx]);
				if (select > ret.length) {
					return null;
				}
				m -= factorials[idx] * select;
				ret[idx] = elmt[select];
				for (int filler = select ; filler < elmt.length - 1; filler++) {
					elmt[filler] = elmt[filler+1];
				}
			}
			return ret;
		} catch (Exception e) {
			e.printStackTrace();
			System.out.println(Arrays.toString(elements) + "\t" + Arrays.toString(factorials) + "\t" + m + "\t" + select + "\t" + Arrays.toString(ret));
			return null;
		}
	}
	
	public static long toLong (int[] digits) {
		long factor = 1;
		long ret = 0;
		for (int x = digits.length - 1 ; x >= 0 ; x--) {
			System.out.println(factor + " * " + (long)digits[x] + " = " + factor * (long)digits[x] + "(" + ret + ")");
			ret += factor * (long)digits[x];
			factor *= 10;
		}
		return ret;
	}
	
	public static void main(String[] args) {
		CombinationGenerator gen = new CombinationGenerator(4);
		for (int idx = 0 ; idx < 20 ; idx++) {
			System.out.println(Arrays.toString(gen.getCombination(idx)));
		}
	}
}
